ebab7d0da53c51438720d60c6e2e467c - /page/wikibook/entry.mu

Micron Document

Livres et Wikis | Archives | Info

🔍Search

Prony's method

9.4 KB · ⇊ 4 parts · ⤓ Micron 9.4 KB · ⤓ HTML 89.3 KB

layout: Wide · Narrow · Centered

──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────

top

Prony analysis (Prony's method) was developed by Gaspard Riche de Prony in 1795. However, practical use of the method awaited the digital computer.cite-ref-1[1] Similar to the Fourier transform, Prony's method extracts valuable information from a uniformly sampled signal and builds a series of damped complex exponentials or damped sinusoids. This allows the estimation of frequency, amplitude, phase and damping components of a signal.

Contents

• The method

• Representations

• See also

• Notes

• References

The method

Let f ( t ) {\displaystyle f(t)} be a signal consisting of N {\displaystyle N} evenly spaced samples. Prony's method fits a function

f ^ ( t ) = ∑ i = 1 N A i e σ i t cos ⁡ ( ω i t + ϕ i ) {\displaystyle {\hat {f}}(t)=\sum _{i=1}^{N}A_{i}e^{\sigma _{i}t}\cos(\omega _{i}t+\phi _{i})}

to the observed f ( t ) {\displaystyle f(t)} . After some manipulation utilizing Euler's formula, the following result is obtained, which allows more direct computation of terms:

f ^ ( t ) = ∑ i = 1 N 1 2 A i ( e j ϕ i e λ i + t + e − j ϕ i e λ i − t ) , {\displaystyle {\begin{aligned}{\hat {f}}(t)=\sum _{i=1}^{N}{\tfrac {1}{2}}A_{i}\left(e^{j\phi _{i}}e^{\lambda _{i}^{+}t}+e^{-j\phi _{i}}e^{\lambda _{i}^{-}t}\right),\end{aligned}}}

where

λ i ± = σ i ± j ω i {\displaystyle \lambda _{i}^{\pm }=\sigma _{i}\pm j\omega _{i}} are the eigenvalues of the system,

σ i = − ω 0 , i ξ i {\displaystyle \sigma _{i}=-\omega _{0,i}\xi _{i}} are the damping components,

ω i = ω 0 , i 1 − ξ i 2 {\displaystyle \omega _{i}=\omega _{0,i}{\sqrt {1-\xi _{i}^{2}}}} are the angular-frequency components,

ϕ i {\displaystyle \phi _{i}} are the phase components,

A i {\displaystyle A_{i}} are the amplitude components of the series,

j {\displaystyle j} is the imaginary unit ( j 2 = − 1 {\displaystyle j^{2}=-1} ).

Representations

Prony's method is essentially a decomposition of a signal with M {\displaystyle M} complex exponentials via the following process:

Regularly sample f ^ ( t ) {\displaystyle {\hat {f}}(t)} so that the n {\displaystyle n} -th of N {\displaystyle N} samples may be written as

F n = f ^ ( Δ t n ) = ∑ m = 1 M B m e λ m Δ t n , n = 0 , … , N − 1. {\displaystyle F_{n}={\hat {f}}(\Delta _{t}n)=\sum _{m=1}^{M}\mathrm {B} _{m}e^{\lambda _{m}\Delta _{t}n},\quad n=0,\dots ,N-1.}

If f ^ ( t ) {\displaystyle {\hat {f}}(t)} happens to consist of damped sinusoids, then there will be pairs of complex exponentials such that

B i ( 1 ) = 1 2 A i e ϕ i j , B i ( 2 ) = 1 2 A i e − ϕ i j , λ i ( 1 ) = σ i + j ω i , λ i ( 2 ) = σ i − j ω i , {\displaystyle {\begin{aligned}\mathrm {B} _{i}^{(1)}&={\tfrac {1}{2}}A_{i}e^{\phi _{i}j},\\\mathrm {B} _{i}^{(2)}&={\tfrac {1}{2}}A_{i}e^{-\phi _{i}j},\\\lambda _{i}^{(1)}&=\sigma _{i}+j\omega _{i},\\\lambda _{i}^{(2)}&=\sigma _{i}-j\omega _{i},\end{aligned}}}

where

B i ( 1 ) e λ i ( 1 ) t + B i ( 2 ) e λ i ( 2 ) t = 1 2 A i e ϕ i j e ( σ i + j ω i ) t + 1 2 A i e − ϕ i j e ( σ i − j ω i ) t = A i e σ i t cos ⁡ ( ω i t + ϕ i ) . {\displaystyle {\begin{aligned}\mathrm {B} _{i}^{(1)}e^{\lambda _{i}^{(1)}t}+\mathrm {B} _{i}^{(2)}e^{\lambda _{i}^{(2)}t}&={\tfrac {1}{2}}A_{i}e^{\phi _{i}j}e^{(\sigma _{i}+j\omega _{i})t}+{\tfrac {1}{2}}A_{i}e^{-\phi _{i}j}e^{(\sigma _{i}-j\omega _{i})t}\\&=A_{i}e^{\sigma _{i}t}\cos(\omega _{i}t+\phi _{i}).\end{aligned}}}

Because the summation of complex exponentials is the homogeneous solution to a linear difference equation, the following difference equation will exist:

f ^ ( Δ t n ) = ∑ m = 1 M f ^ [ Δ t ( n − m ) ] P m , n = M , … , N − 1. {\displaystyle {\hat {f}}(\Delta _{t}n)=\sum _{m=1}^{M}{\hat {f}}[\Delta _{t}(n-m)]P_{m},\quad n=M,\dots ,N-1.}

The key to Prony's Method is that the coefficients in the difference equation are related to the following polynomial:

z M − P 1 z M − 1 − ⋯ − P M = ∏ m = 1 M ( z − e λ m ) . {\displaystyle z^{M}-P_{1}z^{M-1}-\dots -P_{M}=\prod _{m=1}^{M}\left(z-e^{\lambda _{m}}\right).}

These facts lead to the following three steps within Prony's method:

1) Construct and solve the matrix equation for the P m {\displaystyle P_{m}} values:

[ F M ⋮ F N − 1 ] = [ F M − 1 … F 0 ⋮ ⋱ ⋮ F N − 2 … F N − M − 1 ] [ P 1 ⋮ P M ] . {\displaystyle {\begin{bmatrix}F_{M}\\\vdots \\F_{N-1}\end{bmatrix}}={\begin{bmatrix}F_{M-1}&\dots &F_{0}\\\vdots &\ddots &\vdots \\F_{N-2}&\dots &F_{N-M-1}\end{bmatrix}}{\begin{bmatrix}P_{1}\\\vdots \\P_{M}\end{bmatrix}}.}

Note that if N ≠ 2 M {\displaystyle N\neq 2M} , a generalized matrix inverse may be needed to find the values P m {\displaystyle P_{m}} .

2) After finding the P m {\displaystyle P_{m}} values, find the roots (numerically if necessary) of the polynomial

z M − P 1 z M − 1 − ⋯ − P M . {\displaystyle z^{M}-P_{1}z^{M-1}-\dots -P_{M}.}

The m {\displaystyle m} -th root of this polynomial will be equal to e λ m {\displaystyle e^{\lambda _{m}}} .

3) With the e λ m {\displaystyle e^{\lambda _{m}}} values, the F n {\displaystyle F_{n}} values are part of a system of linear equations that may be used to solve for the B m {\displaystyle \mathrm {B} _{m}} values:

[ F k 1 ⋮ F k M ] = [ ( e λ 1 ) k 1 … ( e λ M ) k 1 ⋮ ⋱ ⋮ ( e λ 1 ) k M … ( e λ M ) k M ] [ B 1 ⋮ B M ] , {\displaystyle {\begin{bmatrix}F_{k_{1}}\\\vdots \\F_{k_{M}}\end{bmatrix}}={\begin{bmatrix}(e^{\lambda _{1}})^{k_{1}}&\dots &(e^{\lambda _{M}})^{k_{1}}\\\vdots &\ddots &\vdots \\(e^{\lambda _{1}})^{k_{M}}&\dots &(e^{\lambda _{M}})^{k_{M}}\end{bmatrix}}{\begin{bmatrix}\mathrm {B} _{1}\\\vdots \\\mathrm {B} _{M}\end{bmatrix}},}

where M {\displaystyle M} unique values k i {\displaystyle k_{i}} are used. It is possible to use a generalized matrix inverse if more than M {\displaystyle M} samples are used.

Note that solving for λ m {\displaystyle \lambda _{m}} will yield ambiguities, since only e λ m {\displaystyle e^{\lambda _{m}}} was solved for, and e λ m = e λ m + q 2 π j {\displaystyle e^{\lambda _{m}}=e^{\lambda _{m}\,+\,q2\pi j}} for an integer q {\displaystyle q} . This leads to the same Nyquist sampling criteria that discrete Fourier transforms are subject to

| Im ⁡ ( λ m ) | = | ω m | < π Δ t . {\displaystyle \left|\operatorname {Im} (\lambda _{m})\right|=\left|\omega _{m}\right|<{\frac {\pi }{\Delta _{t}}}.}